package Algorithm.Array;

import java.util.Arrays;

/**
 * @Author ykeezy
 * @Date：2024/6/68:51
 * @PacakageName：
 * @ClassName：2024/6/6
 * @Description：有序数组的平方
 * @Version 1.0
 */
class SortedSqaures {

    //给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
    public static int[] doublePointerSortedSquares(int[] nums){
        //双指针法：newRight指针指向newNums的最高位用于接收原数组剩余元素平方的最大值，每接收一位right就向左移动一位，
        //        由于原数组是非递减顺序排列，故其元素平方后的最大值只会出现在数组的两端，故设置两个指针 left、right，
        //        left指向nums的最低位，right指向nums的最高位，比较left所指元素平方和right所指元素平方的大小，大者存入
        //        newNums，每比较一次，指向大者的指针都会向左，或右移动一位，继续比较元素平方最大值，直到nums被遍历完毕，
        //        得到的newNums就是nums的元素平方后再进行排序的数组。 时间复杂度O(n),空间复杂度O(n)
        //声明一个长度与nums一样的数组用于接收平方后的元素
        int[] newNums = new int[nums.length];
        int left = 0;
        int newRight = nums.length - 1;
        int right = nums.length - 1;
        for (int i = 0; i <= nums.length - 1; i++) {
            if (nums[left] * nums[left] > nums[right] * nums[right]){
                newNums[newRight--] = nums[left] * nums[left];
                left ++;
            }else {
                newNums[newRight--] = nums[right] * nums[right];
                right --;

            }

        }

        return newNums;

    }

    public static int[] rageSortedSquares(int[] nums){
        //暴力法，先将元素换成平方，再对整个数组进行排序
        //时间复杂度O(n + nlogn), 空间复杂度O(n)
        for (int left = 0; left <= nums.length - 1; left++) {
            nums[left] *= nums[left];

        }

        //Arrays类中的快速排序算法
        Arrays.sort(nums);
        return nums;

    }


    public static void main(String[] args) {
        for (int left:rageSortedSquares(new int[]{-4,-1,0,3,10})
             ) {
            System.out.println(left);
        }

    }

}
